package com.java.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 插入排序
 */
public class InsertSort {


    public static void main(String[] args) {

//        int[] arr = {4,-1,6,1,9,3};

        //随机产生一个数组
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }

        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(date1);

        System.out.println("排序前的时间："+date1Str);
        insertSort2(arr);

        Date date2 = new Date();
        SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date2Str = simpleDateFormat2.format(date2);
        System.out.println("排序后的时间："+date2Str);
    }


    /**
     *两种插入排序的代码，但这种的效率比上一种要高很多
     */
    public static void insertSort2(int[] arr){

        int insertVal = 0;
        int insertIndex = 0;

        //插入排序是从第二个元素往前面的元素比较，所以大的循环索引从 1 开始
        for (int i = 1; i < arr.length; i++) {

            //后面的数依次和前面的数比较，所以是 =i
            insertVal = arr[i]; //
            insertIndex = i - 1; //即 arr[i] 前一个下标

            //insertIndex >= 0 : 保证在给insertIndex找插入位置时不越界
            //insertVal < arr[insertIndex] :要插入的数小于上一个数 ，待插入的数还没有找到插入的位置
            //
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) { //如果是从大到小insertVal > arr[insertIndex]
                //就需将insertIndex后移（因为拿出来比较的数比前面的数要小）
                arr[insertIndex + 1] = arr[insertIndex];
                //索引-- , 继续向前面的值比较
                insertIndex--;
            }

            /**
             * [5 , 8]  索引0=5 ； 索引1=8
             * insertVal = arr[1]=8 ；insertIndex = i - 1 =索引：0=>值：5
             *
             * insertVal < arr[insertIndex] 8<5如果为true则还在while中，所以索引为insertIndex索引的值要后移 ， 因为数组长度可能有多个所以需要insertIndex--
             * insertVal < arr[insertIndex] 8<5为false则直接跳出while，自己的索引就是自己的，不需要改变arr[insertIndex+1]=8
             *
             */
            //当退出while循环后，说明插入的位置找到 insertIndex + 1
            arr[insertIndex + 1] = insertVal;


//            System.out.println(Arrays.toString(arr));

        }
    }




    //插入排序
    public static void insertSort(int[] arr){

        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 ; j--) {
                if (arr[j] < arr[j-1]){
                    int temp = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
//            System.out.println(Arrays.toString(arr));
        }



    }



}
